package list.skiplist;

import java.util.Random;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-03 11:34:20
 */
/*
跳跃表实现
    1、每次在底层插入一个数据之后随机判断是否需要提高层数
 */
public class SkipList {

    // level 指针，levelHead到levelTail的节点数代表了最大层数
    SkipListNode levelHead;
    SkipListNode levelTail;

    // 元素的数量
    int count;

    // 最大高度
    int maxLevel;

    public SkipList(){
        levelHead = levelTail = new SkipListNode();
    }

    public void insert(int[] data){
        for (int i = 0; i < data.length; i++) {
            insert(data[i]);
        }
    }

    public void insert(int data){
        SkipListNode tempNode = levelTail;
        SkipListNode newSkipListNode = new SkipListNode(data);
        // 有序双向链表
        while(tempNode.next != null){
            if(tempNode.next.data < newSkipListNode.data){
                tempNode = tempNode.next;
            }else{
                break;
            }
        }
        // 链表为空或者插入链表尾
        if (tempNode.next == null){
            tempNode.next = newSkipListNode;
            newSkipListNode.pre = tempNode;
        }else{// 中间位置
            tempNode.next.pre = newSkipListNode;
            newSkipListNode.pre = tempNode;
            newSkipListNode.next = tempNode.next;
            tempNode.next = newSkipListNode;
        }
        count++;
        // 是否要增加层数
        int currentLevel = 1;
        maxLevel = (int)(Math.log(count) / Math.log(2)) + 1;
        // 最大层数为logn
        while(currentLevel < maxLevel){
            // 随机决定是否提高层数
            if (new Random().nextInt(10) > 4){
                // 增加层数
                currentLevel++;
                if (currentLevel > maxLevel) break;
                addLevel(newSkipListNode);
            }else{
                // 结束插入操作
                break;
            }
        }

    }

    public void insert2(int data){
        SkipListNode newSkipListNode = new SkipListNode(data);
        // 有序双向链表
        SkipListNode tempNode = levelTail.next;
        if(tempNode == null){// 链表为null
            levelTail.next = newSkipListNode;
            newSkipListNode.pre = levelTail;
        }else{
            while(tempNode.next != null && tempNode.data < data){
                tempNode = tempNode.next;
            }
            if(tempNode.next == null){
                // 结尾元素
                if(tempNode.data < data){
                    tempNode.next = newSkipListNode;
                    newSkipListNode.pre = tempNode;
                }else{
                    // 结尾元素，且小于结尾元素
                    tempNode.pre.next = newSkipListNode;
                    newSkipListNode.next = tempNode;
                    newSkipListNode.pre = tempNode.pre;
                    tempNode.pre = newSkipListNode;
                }
            }else{
                if(tempNode.pre == levelTail){
                    // 第一个元素
                    levelTail.next = newSkipListNode;
                    newSkipListNode.pre = levelTail;
                    tempNode.pre = newSkipListNode;
                    newSkipListNode.next = tempNode;
                }else{
                    // 中间元素
                    tempNode.next.pre = newSkipListNode;
                    newSkipListNode.pre = tempNode;
                    newSkipListNode.next = tempNode.next;
                    tempNode.next = newSkipListNode;
                }
            }
        }
        count++;
        // 是否要增加层数
        int currentLevel = 1;
        maxLevel = (int)(Math.log(count) / Math.log(2)) + 1;
        while(currentLevel < maxLevel){
            if (new Random().nextInt(10) > 4){
                // 增加层数
                currentLevel++;
                if (currentLevel > maxLevel) break;
                addLevel(newSkipListNode);
            }else{
                // 结束插入操作
                break;
            }
        }

    }

    public void addLevel(SkipListNode currentSkipListNode){

        SkipListNode currentSkipListNodeNewLevelNode = new SkipListNode(currentSkipListNode.data);
        SkipListNode tempCurrentListNode = currentSkipListNode;
        SkipListNode tempLevelTail = levelTail;

        // level大于1 ，且该节点的层数与最大层数相同
        while (tempCurrentListNode.up != null){
            tempCurrentListNode = tempCurrentListNode.up;
            if (tempLevelTail.up != null){
                tempLevelTail = tempLevelTail.up;
            }
        }
        // level大于1, 当前节点level等于最大level
        if (tempLevelTail.up != null){
            tempLevelTail = tempLevelTail.up;
        }else{// level等于1时新增
            SkipListNode newLevelNode = new SkipListNode();
            tempLevelTail.up = newLevelNode;
            newLevelNode.below = tempLevelTail;
            levelHead = newLevelNode;
            tempLevelTail = newLevelNode;
        }
        tempCurrentListNode.up = currentSkipListNodeNewLevelNode;
        currentSkipListNodeNewLevelNode.below = tempCurrentListNode;

        if(tempLevelTail.next == null){
            // 新level
            tempLevelTail.next = currentSkipListNodeNewLevelNode;
            currentSkipListNodeNewLevelNode.pre = tempLevelTail;
        }else{
            // 查找新增层数的位置
            while (tempLevelTail.next != null && tempLevelTail.next.data < currentSkipListNode.data){
                tempLevelTail = tempLevelTail.next;
            }
            if(tempLevelTail.next == null){
                // 最后
                if (tempCurrentListNode.data > currentSkipListNode.data){
                    tempLevelTail.next = currentSkipListNodeNewLevelNode;
                    currentSkipListNodeNewLevelNode.pre = tempLevelTail;
                }else{
                    tempLevelTail.next = currentSkipListNodeNewLevelNode;
                    currentSkipListNodeNewLevelNode.pre = tempLevelTail;
                }
            }else{
                // 中间位置
                tempLevelTail.next.pre = currentSkipListNodeNewLevelNode;
                currentSkipListNodeNewLevelNode.pre = tempLevelTail;
                currentSkipListNodeNewLevelNode.next = tempLevelTail.next;
                tempLevelTail.next = currentSkipListNodeNewLevelNode;
            }
        }
    }

    public int search(int data){
        int searchCount = 0;
        SkipListNode tempNode = levelHead;
        if (tempNode.next == null) return 0;
        while(tempNode != null){
            searchCount++;
            if (tempNode.next != null && tempNode.next.data == data) return searchCount;
            else if (tempNode.next != null && tempNode.next.data > data) tempNode = tempNode.below;
            else {
                if (tempNode.next == null){
                    tempNode = tempNode.below;
                }else{
                    tempNode = tempNode.next;
                }
            }
        }

        return -1;
    }
    ////////////////////////////////////test
    public static void main(String[] args) {
        int[] data = new int[]{2, 3, 1, 4, 5, 7, 6, 9, 8};
        SkipList skipList = new SkipList();
        skipList.insert(data);

        //System.out.println((int)(Math.log(7) / Math.log(2)));

//        for (int i = 0; i < 10; i++) {
//            System.out.println("new Random().nextInt(10) = " + new Random().nextInt(10));
//        }

        for (int i = 0; i < 10; i++) {
            System.out.println("skipList = " + skipList.search(i));
        }

        System.out.println("skipList = " + skipList);
    }

}
